package huawei.year2016;

import java.util.*;

/**
 * Created by Hyman on 2017/3/16.
 * <p>
 * <p>
 * 有一个数组a[N]顺序存放0~N-1，要求每隔两个数删掉一个数，到末尾时循环至开头继续进行，求最后一个被删掉的数的原始下标位置。
 * 以8个数(N=7)为例:｛0，1，2，3，4，5，6，7｝，0->1->2(删除)->3->4->5(删除)->6->7->0(删除),如此循环直到最后一个数被删除。
 * <p>
 * 输入描述: 每组数据为一行一个整数n(小于等于1000)，为数组成员数,如果大于1000，则对a[999]进行计算。
 * 输出描述: 每一行输出最后一个被删掉的数的原始下标位置
 * <p>
 * 输入例子: 8
 * 输出例子: 6
 */
public class DelNumberEveryTwoCount {


    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine();

            int len = Integer.parseInt(line);
            //int lastIndex = getLastDelPos(len > 1000 ? 999 : len);
            int lastIndex = getLastDelPos2(len > 1000 ? 999 : len);

            System.out.println(lastIndex);
        }
        scanner.close();
    }

    private static int getLastDelPos(int len) {

        int arr[] = new int[len];

        for (int i = 0; i < len; i += 2) {
            arr[i] = i;
        }

        final int delFlag = len; //标记被删除
        final int step = 2;    //步长
        int curSize = len;       //删一个数则减一
        int curPos = 0;        //当前遍历的位置
        int count = 0;
        int lastIndex = 0;

        while (curSize != 0) {

            if (arr[curPos] != delFlag) {

                if (count == step) {

                    arr[curPos] = delFlag;
                    curSize--;

                    lastIndex = curPos;
                    count = 0;

                } else {
                    count++;
                }
            }

            curPos = (curPos + 1) % len;
        }

        return lastIndex;
    }

    /**
     * 用队列模拟，队首取数，用一个计数器计数，隔2个删一个，其他的重新放到队尾
     *
     * @param len
     * @return
     */
    private static int getLastDelPos2(int len) {

        Queue<Integer> queue = new ArrayDeque<>(1000);

        for (int i = 0; i < len; i++) {
            queue.add(i);
        }

        int count = 0;
        int position = -1;
        final int step = 2;

        while(!queue.isEmpty()) {

            position = queue.poll();

            if(count == step) {
                count = 0;
            } else {
                if(queue.isEmpty()) {
                    break;
                }
                count++;
                queue.add(position);
            }
        }

        return position;
    }
}
